Next greater node in linked list [Mono Stack]

Time: O(N); Space: O(N); medium

We are given a linked list with head as the first node. Let’s number the nodes in the list: node_1, node_2, node_3, … etc.

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.

Example 1:

Input: head = [2,1,5]

Output: [5,5,0]

Example 2:

Input: head = [2,7,4,3,5]

Output: [7,0,5,5,0]

Example 3:

Input: head = [1,7,5,1,9,2,5,1]

Output: [7,9,9,9,0,5,0,0]

Constraints:

  1. 1 <= node.val <= 10^9 for each node in the linked list.

  2. The given list has length in the range [0, 10000].

[1]:

class ListNode(object):
    """
    Definition for singly-linked list
    """
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution1(object):
    def nextLargerNodes(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        result, stk = [], []

        while head:
            while stk and stk[-1][1] < head.val:
                result[stk.pop()[0]] = head.val
            stk.append([len(result), head.val])
            result.append(0)
            head = head.next

        return result

[2]:

s = Solution1()
head = ListNode(2)
head.next = ListNode(1)
head.next.next = ListNode(5)
assert s.nextLargerNodes(head) == [5,5,0]

head = ListNode(2)
head.next = ListNode(7)
head.next.next = ListNode(4)
head.next.next.next = ListNode(3)
head.next.next.next.next = ListNode(5)
assert s.nextLargerNodes(head) == [7,0,5,5,0]

head = ListNode(1)
head.next = ListNode(7)
head.next.next = ListNode(5)
head.next.next.next = ListNode(1)
head.next.next.next.next = ListNode(9)
head.next.next.next.next.next = ListNode(2)
head.next.next.next.next.next.next = ListNode(5)
head.next.next.next.next.next.next.next = ListNode(1)
assert s.nextLargerNodes(head) == [7,9,9,9,0,5,0,0]